\documentclass[a4paper, notitlepage]{report}
 
\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}
 
\oddsidemargin=-1mm
\evensidemargin=-1mm
\setlength{\textwidth}{6.5in}
\addtolength{\voffset}{-4pt}
\addtolength{\textheight}{+0.9in}
\addtolength{\hoffset}{-5pt}
\pagestyle{empty}
%\textwidth = 1592pt
%\hoffset = 1pt
%\marginparwidth = 1pt
\begin{document}

\section*{Описание конкурсной работы}
 
\subsection*{Авторы}

\begin{itemize}
\item Заикина Екатерина Александровна
\item Мамич Ксения Вадимовна
\end{itemize}

Студенты 4-ого курса НИУ ИТМО, факультета Информационных технологий и программирования, кафедры Информационных систем.
Также учимся в Computer Science Center (направление Разработка программного обеспечения).

\subsection*{Постановка задачи}
В двух строках, состоящих их символов $A$, $T$, $G$, $C$, найти максимально длинные совпадающие подстроки не короче $M$. 
На вход дается число $M$, \emph{ref-}файл и имена нескольких \emph{input-}файлов со строками.

\subsection*{Последовательный алгоритм}
\begin{enumerate}
\item Считать входные строки из файлов. Символ $A$ в программе представлен кодом 0, $T$ ~--- 1, $G$ ~--- 2, $C$ ~--- 3.
\item Для каждой подстроки $subref_{i}$ длины $blockSize$ \emph{ref-}строки вычислить \emph{hash-}функцию. Причем $hash(s_{i + 1})$ 
вычисляется из $hash(s_{i})$ за константное время путём битового сдвига на 2 позиции и прибавления кода нового символа. 
\item На основе полученных значений \emph{hash-}функции построить \emph{hash-}таблицу, хранящую списки индексов соответствующих подстрок.
\item Для всех подстрок $subinput_{j}$ длины $blockSize$ из \emph{input-}строки вычислить
значение той же \emph{hash-}функции и проверить в \emph{hash-}таблице наличие соответствующего списка индексов (обозначим его $lst$). 
\item Если для некоторой $subinput_{j}$ в таблице найден $lst$, то для всех пар $(j, lst[k])$ проверить, не являются ли они началами максимально
длинных совпадающих подстрок (просто идти вправо по последовательностям, начиная с индекса $j$ в \emph{input-}строке и $lst[k]$ ~--- в
\emph{ref-}строке пока символы из обеих строк совпадают), и в случае успеха, добавить полученные результаты в ответ.
\item Отсортировать, отфильтровать и вывести результат таким образом, чтобы он совпадал с ответом референсного решения. 
\end{enumerate}

В итоговой программе были попарно объединены в общие циклы пункты 2 и 3, а также 4 и 5. 

\subsection*{Работа параллельной программы}
Для написания многопоточной версии была использована библиотека Intel TBB. Задействованы алгоритмы \emph{parallel\_for} и \emph{parallel\_sort}. Также была использована функция \emph{parallel\_pipeline}.

В приведенном последовательном алгоритме практически нет подзадач, зависящих от выполнения предыдущих. Ясно, что \emph{hash}-функции для подстрок можно считать независимо в разных потоках. Также можно распараллелить проверку на то, является ли текущая позиция началом одного из ответов или нет.

Проблемы возникли с многопоточным построением \emph{hash-}таблицы. Если для синхронизации \emph{hash-}таблицы использовать один мьютекс, то из-за частых операций взятия/снятия блокировки польза от многопоточности сводится на нет.
Был заведен массив мьютексов длины \emph{256 * количество потоков} (число 256 выбрано из-за любви к круглым числам). 
Мьютекс с индексом $i$ блокируется, когда в таблицу добавляется элемент с ключом, равным $i$ по модулю количества мьютексов. 
То есть, каждый мьютекс блокирует не всю таблицу, а лишь несколько "строк" в ней. Это снизило время ожидания при построении таблицы.

Pipeline включает в себя два фильтра: первый считывает данные из файлов (в один поток ~--- \emph{serial\_in\_order}), второй производит параллельную обработку (\emph{parallel}).

\end{document}
